﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _14.QuickSort
{
    class QuickSort
    {
        static void Main(string[] args)
        {
            Console.Write("N of array:");
            int n = int.Parse(Console.ReadLine());

            string[] letters = new string[n];
            for (int i = 0; i < n; i++)
            {
                Console.Write("letters[{0}]: ", i);
                letters[i] = Console.ReadLine();
            }

            
            Console.WriteLine("{0} ","BEFORE");
            for (int i = 0; i < letters.Length; i++)
            {
                Console.WriteLine("[{0}]={1,4} |",i,letters[i]);
            }

            Console.WriteLine();

            
            Quicksort(letters, 0, letters.Length - 1);

            Console.SetCursorPosition(2 * n+1, n+1);
            Console.WriteLine("{0} ", "NOW");
            

            for (int i = 0; i < letters.Length; i++)
            {
                Console.SetCursorPosition(2 * n+1, n + i+2);
                
                Console.Write("[{0}]={1}", i, letters[i]);
            }
           

            Console.WriteLine();
        }

        public static void Quicksort(IComparable[] newLetters, int left, int right)
        {
            int i = left, j = right;
            IComparable pivot = newLetters[(left + right) / 2];

            while (i <= j)
            {
                while (newLetters[i].CompareTo(pivot) < 0)
                {
                    i++;
                }

                while (newLetters[j].CompareTo(pivot) > 0)
                {
                    j--;
                }

                if (i <= j)
                {
                    
                    IComparable tmp = newLetters[i];
                    newLetters[i] = newLetters[j];
                    newLetters[j] = tmp;

                    i++;
                    j--;
                }
            }

           
            if (left < j)
            {
                Quicksort(newLetters, left, j);
            }

            if (i < right)
            {
                Quicksort(newLetters, i, right);
            }
        }

    }
}